图论经典算法(通俗易懂):最短路径和最小生成树 | 您所在的位置:网站首页 › 图论 道路 最小开销 › 图论经典算法(通俗易懂):最短路径和最小生成树 |
一、最短路问题
求图的最短路问题,几乎是图论的必学内容,而且在算法分析与设计中也会涉及。很多书上内容,实在没法看,我们的图论教材,更是编的非常糟糕,吐槽,为啥要用自己学校编的破教材,不过据说下一届终于要换书了。 言归正传,开始说明最短路问题。 1.问题描述:对一幅图G,我们对每一条边赋权w(e),成为一个赋权图。H是G的一个子图,则W(H) = sigma(w(e)),也就是对每条边的权求和。寻找从一个点a到另一个b的一个子图,使得权和最小,即为最短路问题。 2.算法描述: Dijkstra(迪杰斯特拉算法算法):
其实就是不断求一个点集合中的每个点,和与他相邻点最短路的最小值。我们还是从实例出发,更容易讲解。我会把上述步骤,拆解为多步。我们求下面这个图从A到L的最短路。 关于算法的实现可以在参考资料中找到。 二、最小生成树 问题描述同样在一个连通赋权图中,寻找一颗生成树使得权和最小。 此算法比较简单,很容易理解。 算法描述:Kruskal算法: 比如,寻找下图的最小生成树。 1.https://blog.csdn.net/u012469987/article/details/51319574 2.https://www.cnblogs.com/hxsyl/p/3270401.html |
CopyRight 2018-2019 实验室设备网 版权所有 |